package com.captain.leetcode.二维数组;

import java.util.*;

/**
 * @author captain
 * @Des 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
 * @Date 2021/7/28 22:16
 */
public class 合并区间56 {
    public static void main(String[] args) {
        int[][] arr = new int[][]{{1, 2}, {3, 5},{6,7},{8,10},{12,16},{4,8}};
        for (int[] ints : new 合并区间56().merge(arr)) {
            System.out.println(Arrays.toString(ints));
        }
    }
//        [1][3]
//        [2][6]
//        [8][10]
//        [15][18]

    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return null;
        //排序
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        int start = intervals[0][0];
        //一行一行的遍历进行比较
        int len = intervals.length;

        List<int[]> res = new ArrayList<>();
        for (int i = 1; i < len; i++) {
            int pre = intervals[i - 1][1];
            int next = intervals[i][0];
            if (pre < next) {
                res.add(new int[]{start, intervals[i - 1][1]});
                start = intervals[i][0];
            } else {
                intervals[i][1] = Math.max(intervals[i - 1][1], intervals[i][1]);
            }
        }
        res.add(new int[]{start, intervals[intervals.length - 1][1]});
        return res.toArray(new int[res.size()][]);
    }
}
